package cn.arnold.tree;

public class BinaryTree {
    public static void main(String[] args) {
        BinaryT binarytree = new BinaryT();
        // 创建节点
        HeroNode node1 = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "卢俊义");
        HeroNode node3 = new HeroNode(3, "吴用");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "林冲");
        HeroNode node6 = new HeroNode(6, "林冲");
        HeroNode node7 = new HeroNode(7, "林冲");
        HeroNode node8 = new HeroNode(8, "林冲");
        HeroNode node9 = new HeroNode(9, "林冲");
        // 手动创建二叉树：创建节点关系
        binarytree.setRoot(node4);
        node4.setLeft(node1);
        node1.setLeft(node3);
        node1.setRight(node6);
        node3.setLeft(node5);
        node6.setRight(node7);
        node5.setLeft(node2);
        node5.setRight(node8);
        node7.setRight(node9);
        System.out.println("前序遍历");
        binarytree.preOrder();
        HeroNode heroNode1 = binarytree.preSearch(3);
        System.out.println("前序查找：" + heroNode1);
        System.out.println("中序遍历");
        binarytree.midOrder();
        HeroNode heroNode2 = binarytree.midSearch(4);
        System.out.println("中序查找：" + heroNode2);
        System.out.println("后序遍历");
        binarytree.postOrder();
        HeroNode heroNode3 = binarytree.postSearch(2);
        System.out.println("后序遍历：" + heroNode3);
        binarytree.remove(3);
        binarytree.postOrder();
    }


}


// 定义二叉树
class BinaryT {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    // 前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空...");
        }
    }

    // 中序遍历
    public void midOrder() {
        if (this.root != null) {
            this.root.midOrder();
        } else {
            System.out.println("二叉树为空...");
        }
    }

    // 后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空...");
        }
    }

    // 前序查找
    public HeroNode preSearch(int id) {
        if (this.root == null) {
            System.out.println("二叉树为空...");
            return null;
        } else {
            return this.root.preSearch(id);
        }
    }

    // 中序查找
    public HeroNode midSearch(int id) {
        if (this.root == null) {
            System.out.println("二叉树为空...");
            return null;
        } else {
            return this.root.midSearch(id);
        }
    }

    // 后序查找
    public HeroNode postSearch(int id) {
        if (this.root == null) {
            System.out.println("二叉树为空...");
            return null;
        } else {
            return this.root.postSearch(id);
        }
    }

    // 删除节点
    public void remove(int id){
        // 如果树是空树或者只有一个root节点
        if (this.root == null) {
            System.out.println("二叉树为空...");
            return ;
        }
        // 只有一个root节点
        if (this.root.getLeft()==null && this.root.getRight()==null){
            this.root=null;
        }
        this.root.remove(id);
    }
}

// 节点对象
class HeroNode {
    private int id;
    private String name;
    private HeroNode left;      //左节点，默认为null
    private HeroNode right;     //右节点，默认为null

    // 构造器
    public HeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    // 前序遍历:父节点---左子树---右子树
    public void preOrder() {
        // 父节点
        System.out.println(this);
        // 左子树递归
        if (this.left != null) {
            this.left.preOrder();
        }
        // 右子树递归
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    // 中序遍历:左子树---父节点---右子树
    public void midOrder() {
        // 左子树递归
        if (this.left != null) {
            this.left.midOrder();
        }
        // 父节点
        System.out.println(this);
        // 右子树递归
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    // 后遍历:左子树---右子树---父节点
    public void postOrder() {
        // 左子树递归
        if (this.left != null) {
            this.left.postOrder();
        }
        // 右子树递归
        if (this.right != null) {
            this.right.postOrder();
        }
        // 父节点
        System.out.println(this);
    }

    // 前序查找
    public HeroNode preSearch(int id) {
        HeroNode resNode = null;
        // 1. 判断当前节点是否是要查找的节点
        if (this.id == id) {
            return this;
        }
        // 2. 如果不是，则判断当前节点的左子节点是否为空，不为空则递归前序查找
        if (this.left != null) {
            resNode = this.left.preSearch(id);
        }
        if (resNode != null) {     // 左子树前序递归找到
            return resNode;
        }
        // 3. 如果左子树递归没有找到，则判断右节点是否为空，不为空则递归前序查找
        if (this.right != null) {
            resNode = this.right.preSearch(id);
        }
        return resNode;
    }

    // 中序查找
    public HeroNode midSearch(int id) {
        HeroNode resNode = null;
        // 1. 判断当前节点的左子节点是否为空，不为空则递归前序查找
        if (this.left != null) {
            resNode = this.left.midSearch(id);
        }
        if (resNode != null) {     // 左子树前序递归找到
            return resNode;
        }
        // 2. 没有找到则和当前节点比较，当前节点是否是要查找的节点
        if (this.id == id) {
            return this;
        }
        // 3. 如果左子树递归没有找到，则判断右节点是否为空，不为空则递归前序查找
        if (this.right != null) {
            resNode = this.right.midSearch(id);
        }
        return resNode;
    }

    // 后序查找
    public HeroNode postSearch(int id) {
        HeroNode resNode = null;
        // 1. 判断当前节点的左子节点是否为空，不为空则递归前序查找
        if (this.left != null) {
            resNode = this.left.postSearch(id);
        }
        if (resNode != null) {     // 左子树前序递归找到
            return resNode;
        }
        // 2. 如果左子树递归没有找到，则判断右节点是否为空，不为空则递归前序查找
        if (this.right != null) {
            resNode = this.right.postSearch(id);
        }
        if (resNode != null) {     // 右子树前序递归找到
            return resNode;
        }
        // 3. 没有找到则和当前节点比较，当前节点是否是要查找的节点
        if (this.id == id) {
            return this;
        }

        return resNode;
    }

    /**
     * 删除节点
     * 1、如果删除的节点定叶子节点，则删除该节点
     * 2、如果删除的节点是非叶子节点，则删除该子树
     * @param id
     */
    public void remove(int id){

        // 1. 如果当前节点的左子节点不为空且左子节点就是要删除的节点：this.left=null
        if (this.left!=null && this.left.id==id){
            this.left=null;
            return;
        }
        // 2. 如果当前节点的右子节点不为空且右子节点就是要删除的节点：this.right=null
        if (this.right!=null && this.right.id==id){
            this.right=null;
            return;
        }
        // 3. 左子树递归删除
        if (this.left!=null){
            this.left.remove(id);
        }
        // 4. 右子树递归删除
        if (this.right!=null){
            this.right.remove(id);
        }
    }

}